{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Relocate Marbles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sorting #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #排序 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: relocateMarbles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重新放置石块"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;，表示一些石块的初始位置。再给你两个长度<strong>&nbsp;相等</strong>&nbsp;下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>moveFrom</code> 和&nbsp;<code>moveTo</code>&nbsp;。</p>\n",
    "\n",
    "<p>在&nbsp;<code>moveFrom.length</code>&nbsp;次操作内，你可以改变石块的位置。在第&nbsp;<code>i</code>&nbsp;次操作中，你将位置在&nbsp;<code>moveFrom[i]</code>&nbsp;的所有石块移到位置&nbsp;<code>moveTo[i]</code>&nbsp;。</p>\n",
    "\n",
    "<p>完成这些操作后，请你按升序返回所有 <strong>有</strong>&nbsp;石块的位置。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果一个位置至少有一个石块，我们称这个位置 <strong>有</strong>&nbsp;石块。</li>\n",
    "\t<li>一个位置可能会有多个石块。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,6,7,8], moveFrom = [1,7,2], moveTo = [2,9,5]\n",
    "<b>输出：</b>[5,6,8,9]\n",
    "<b>解释：</b>一开始，石块在位置 1,6,7,8 。\n",
    "第 i = 0 步操作中，我们将位置 1 处的石块移到位置 2 处，位置 2,6,7,8 有石块。\n",
    "第 i = 1 步操作中，我们将位置 7 处的石块移到位置 9 处，位置 2,6,8,9 有石块。\n",
    "第 i = 2 步操作中，我们将位置 2 处的石块移到位置 5 处，位置 5,6,8,9 有石块。\n",
    "最后，至少有一个石块的位置为 [5,6,8,9] 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,3,3], moveFrom = [1,3], moveTo = [2,2]\n",
    "<b>输出：</b>[2]\n",
    "<b>解释：</b>一开始，石块在位置 [1,1,3,3] 。\n",
    "第 i = 0 步操作中，我们将位置 1 处的石块移到位置 2 处，有石块的位置为 [2,2,3,3] 。\n",
    "第 i = 1 步操作中，我们将位置 3 处的石块移到位置 2 处，有石块的位置为 [2,2,2,2] 。\n",
    "由于 2 是唯一有石块的位置，我们返回 [2] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= moveFrom.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>moveFrom.length == moveTo.length</code></li>\n",
    "\t<li><code>1 &lt;= nums[i], moveFrom[i], moveTo[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li>测试数据保证在进行第&nbsp;<code>i</code>&nbsp;步操作时，<code>moveFrom[i]</code>&nbsp;处至少有一个石块。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [relocate-marbles](https://leetcode.cn/problems/relocate-marbles/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [relocate-marbles](https://leetcode.cn/problems/relocate-marbles/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,6,7,8]\\n[1,7,2]\\n[2,9,5]', '[1,1,3,3]\\n[1,3]\\n[2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        stones = set(nums)\n",
    "        for i in range(len(moveTo)):\n",
    "            stones.remove(moveFrom[i])\n",
    "            stones.add(moveTo[i])\n",
    "        return sorted(list(stones))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        s=set(nums)\n",
    "        for f,t in zip(moveFrom,moveTo):\n",
    "            s.remove(f)\n",
    "            s.add(t)\n",
    "        return sorted(s)    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        s = set(nums)\n",
    "        for f, t in zip(moveFrom, moveTo):\n",
    "            s.remove(f)\n",
    "            s.add(t)\n",
    "        return sorted(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        s=set(nums)\n",
    "        for a,b in zip(moveFrom,moveTo):\n",
    "            s.remove(a)\n",
    "            s.add(b)\n",
    "        return sorted(list(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        res=set(nums)\n",
    "        for i in range(len(moveFrom)):\n",
    "            res.remove(moveFrom[i])\n",
    "            res.add(moveTo[i])\n",
    "        a=list(res);a.sort()\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        all = set(nums)\n",
    "        for x, y in zip(moveFrom, moveTo):\n",
    "            all.remove(x)\n",
    "            all.add(y)\n",
    "        return sorted(all)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "\n",
    "        s = set(nums)\n",
    "\n",
    "        for ff, tt in zip(moveFrom, moveTo):\n",
    "            if ff not in s:\n",
    "                continue\n",
    "            if ff == tt:\n",
    "                continue\n",
    "\n",
    "            s.add(tt)\n",
    "            s.remove(ff)\n",
    "\n",
    "        ans = list(s)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, a: list[int], b: list[int], c: list[int]) -> list[int]:\n",
    "        n, m = len(a), len(b)\n",
    "        S = set(a)\n",
    "        print(S)\n",
    "        for  i in range(m):\n",
    "            S.discard(b[i])\n",
    "            S.add(c[i])\n",
    "        return sorted(list(S))\n",
    "\n",
    "\n",
    "# problem = Solution()\n",
    "# print(problem.relocateMarbles([1, 1, 3, 3], [1, 3], [2, 2]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        nums = set(nums)\n",
    "        print(nums)\n",
    "        for i,m in enumerate(moveFrom):\n",
    "            nums.remove(m)\n",
    "            nums.add(moveTo[i])\n",
    "        print(nums)\n",
    "        return sorted(list(nums))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        sett=set(nums)\n",
    "        for i in range(len(moveFrom)):\n",
    "            sett.remove(moveFrom[i])\n",
    "            sett.add(moveTo[i])\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        return list(sorted(list(sett)))\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        assert 1 <= len(nums) <= 10**5\n",
    "        assert 1 <= len(moveFrom) <= 10**5\n",
    "        assert len(moveFrom) == len(moveTo)\n",
    "        for i in nums + moveFrom + moveTo:\n",
    "            assert 1 <= i <= 10**9\n",
    "        \n",
    "        nums = set(nums)\n",
    "        for x,y in zip(moveFrom, moveTo):\n",
    "            assert x in nums\n",
    "            nums.remove(x)\n",
    "            nums.add(y)\n",
    "        nums = list(nums)\n",
    "        nums.sort()\n",
    "        return nums\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        l = SortedList(set(nums))\n",
    "        \n",
    "        for m, t in zip(moveFrom, moveTo):\n",
    "            while m in l:\n",
    "                l.remove(m)\n",
    "            if t not in l:\n",
    "                l.add(t)\n",
    "            \n",
    "        return sorted(set(l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        arr = list(set(nums))\n",
    "        s = set(arr)\n",
    "        for x, y in zip(moveFrom, moveTo):\n",
    "            s.remove(x)\n",
    "            s.add(y)\n",
    "        return sorted(list(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        cnt = collections.Counter(nums)\n",
    "        for f, t in zip(moveFrom, moveTo):\n",
    "            if f != t:\n",
    "                cnt[t] += cnt[f]\n",
    "                cnt[f] = 0\n",
    "        ans = []\n",
    "        for x, y in cnt.items():\n",
    "            if y > 0:\n",
    "                ans.append(x)\n",
    "        ans.sort()\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        d = dict(zip(nums, [0] * len(nums)))\n",
    "        for f, t in zip(moveFrom, moveTo):\n",
    "            del d[f]\n",
    "            d[t] = 0\n",
    "        return sorted(d.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        record=dict()\n",
    "        for i in nums:\n",
    "            if i in record:\n",
    "                record[i]+=1\n",
    "            else:\n",
    "                record[i]=1\n",
    "        \n",
    "        for i in range(len(moveFrom)):\n",
    "            if moveTo[i] in record:\n",
    "                record[moveTo[i]]+=record[moveFrom[i]]\n",
    "            else:\n",
    "                record[moveTo[i]]=record[moveFrom[i]]\n",
    "            if moveFrom[i]!=moveTo[i]:\n",
    "                del record[moveFrom[i]]\n",
    "        \n",
    "        ans=[]\n",
    "        for i in record:\n",
    "            ans+=[i]\n",
    "        \n",
    "        ans.sort()\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        arr = Counter()\n",
    "        for i in nums:\n",
    "            arr[i] = 1\n",
    "        for x,y in zip(moveFrom,moveTo):\n",
    "            arr[x] = 0\n",
    "            arr[y] = 1\n",
    "        res = []\n",
    "        for i,j in arr.items():\n",
    "            if j == 1:\n",
    "                res.append(i)\n",
    "        res.sort()        \n",
    "        return res                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        dic = {}\n",
    "        for s, e in zip(moveFrom[::-1], moveTo[::-1]):\n",
    "            if e in dic:\n",
    "                dic[s] = dic[e]\n",
    "            else:\n",
    "                dic[s] = e \n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in dic:\n",
    "                nums[i] = dic[nums[i]]\n",
    "        return sorted(set(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        for f, t in zip(moveFrom, moveTo):\n",
    "            c = cnt[f]\n",
    "            cnt[f] -= c\n",
    "            cnt[t] += c\n",
    "        return sorted([i for i in cnt.keys() if cnt[i] > 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "            要将 from[i] move[i]         \n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums) \n",
    "\n",
    "        for i,j in zip(moveFrom,moveTo):\n",
    "            if i == j: continue\n",
    "            cnt[j]+=cnt[i]\n",
    "            cnt[i]=0\n",
    "        ans = [] \n",
    "        for key,val in cnt.items():\n",
    "            if val:\n",
    "                ans.append(key)\n",
    "        ans.sort() \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        n,ans,mp=len(moveFrom),[],{}\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(moveTo[i] not in mp):ans.append(moveTo[i]);mp[moveTo[i]]=1\n",
    "            mp[moveFrom[i]]=1\n",
    "        for i in nums:\n",
    "            if(i not in mp):ans.append(i);mp[i]=1\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        d = defaultdict(int)\n",
    "        for k in nums:\n",
    "            d[k]+=1\n",
    "        for i in range(len(moveFrom)):\n",
    "            mf,mt=moveFrom[i],moveTo[i]\n",
    "            sb = d[mf]\n",
    "            d[mf]-=sb\n",
    "            d[mt]+=sb\n",
    "        res = sorted([k for k in d if d[k]>=1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import defaultdict\n",
    "\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        def def_value():\n",
    "            return 0\n",
    "        Map = defaultdict(def_value)\n",
    "        for x in nums:\n",
    "            Map[x]+=1\n",
    "        n = len(moveFrom)\n",
    "        # print(Map)\n",
    "        for i in range(n):\n",
    "            if moveFrom[i] == moveTo[i]:\n",
    "                continue\n",
    "            Map[moveTo[i]] += Map[moveFrom[i]]\n",
    "            Map[moveFrom[i]] = 0\n",
    "            # print(moveFrom[i],moveTo[i],Map)\n",
    "        ans = []\n",
    "        for key,value in Map.items():\n",
    "            if value !=0 :\n",
    "                ans.append(key)\n",
    "        ans.sort()\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        counter=Counter(nums)\n",
    "        for i,mf in enumerate(moveFrom):\n",
    "            c1=counter[mf]\n",
    "            counter[mf]=0\n",
    "            counter[moveTo[i]]+=c1\n",
    "        # print(counter)\n",
    "        ans=[]\n",
    "        for key in counter:\n",
    "            # for c in range(counter[key]):\n",
    "            if counter[key]!=0:\n",
    "                ans.append(key)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        nums=set(nums)\n",
    "        for i in range(len(moveFrom)):\n",
    "            nums.remove(moveFrom[i])\n",
    "            nums.add(moveTo[i])\n",
    "        return sorted(list(set(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        n=len(moveFrom)\n",
    "        nums=set(nums)\n",
    "        for i in range(n):\n",
    "            nums.remove(moveFrom[i])\n",
    "            nums.add(moveTo[i])\n",
    "        return sorted(list(set(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        nums = set(nums)\n",
    "        for i in range(len(moveFrom)):\n",
    "            nums.remove(moveFrom[i])\n",
    "            if moveTo[i] not in nums:\n",
    "                nums.add(moveTo[i])\n",
    "        return sorted(list(set(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        counter = collections.defaultdict(int)\n",
    "        for i in nums :\n",
    "            counter[i] += 1\n",
    "        \n",
    "        for i in range(len(moveFrom)) :\n",
    "            mid = counter[moveFrom[i]]\n",
    "            counter[moveFrom[i]] = 0\n",
    "            counter[moveTo[i]] = mid\n",
    "        \n",
    "        print(counter)\n",
    "        res = []\n",
    "        for i in counter.keys() :\n",
    "            if counter[i] != 0 :\n",
    "                res.append(i)\n",
    "        res.sort()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        ss = SortedSet(nums)\n",
    "        for f, t in zip(moveFrom, moveTo):\n",
    "            if f not in ss:\n",
    "                continue\n",
    "            ss.remove(f)\n",
    "            ss.add(t)\n",
    "        return list(ss)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        fa = {}\n",
    "        for x, y in list(zip(moveFrom, moveTo))[::-1]:\n",
    "            if y in fa:\n",
    "                fa[x] = fa[y]\n",
    "            else:\n",
    "                fa[x] = y\n",
    "        ans = []\n",
    "        for x in nums:\n",
    "            if x in fa:\n",
    "                ans.append(fa[x])\n",
    "            else:\n",
    "                ans.append(x)\n",
    "        return sorted(set(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        dic = {}\n",
    "        n = len(moveFrom)\n",
    "        for i in nums:\n",
    "            if i in dic:\n",
    "                dic[i] += 1\n",
    "            else:\n",
    "                dic[i] = 1\n",
    "        for i in range(n):\n",
    "            if moveTo[i] == moveFrom[i]:\n",
    "                continue\n",
    "            if moveTo[i] in dic:\n",
    "                dic[moveTo[i]] += dic[moveFrom[i]]\n",
    "            else:\n",
    "                dic[moveTo[i]] = dic[moveFrom[i]]\n",
    "            dic[moveFrom[i]] = 0\n",
    "        print(dic)\n",
    "        ans = []\n",
    "        for k,d in dic.items():\n",
    "            if d > 0:\n",
    "                ans.append(k)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 给你一个下标从 0 开始的整数数组 nums ，表示一些石块的初始位置。再给你两个长度 相等 下标从 0 开始的整数数组 moveFrom 和 moveTo 。\n",
    "\n",
    "# 在 moveFrom.length 次操作内，你可以改变石块的位置。在第 i 次操作中，你将位置在 moveFrom[i] 的所有石块移到位置 moveTo[i] 。\n",
    "\n",
    "# 完成这些操作后，请你按升序返回所有 有 石块的位置。\n",
    "\n",
    "# 注意：\n",
    "\n",
    "\n",
    "# 如果一个位置至少有一个石块，我们称这个位置 有 石块。\n",
    "# 一个位置可能会有多个石块。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        counter = Counter(set(nums))\n",
    "        for from_, to in zip(moveFrom, moveTo):\n",
    "            counter[from_] = 0\n",
    "            counter[to] += 1\n",
    "        return sorted([k for k, v in counter.items() if v > 0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        dic = {}\n",
    "        n = len(moveFrom)\n",
    "        for i in nums:\n",
    "            if i in dic:\n",
    "                dic[i] += 1\n",
    "            else:\n",
    "                dic[i] = 1\n",
    "        for i in range(n):\n",
    "            if moveTo[i] == moveFrom[i]:\n",
    "                continue\n",
    "            if moveTo[i] in dic:\n",
    "                dic[moveTo[i]] += dic[moveFrom[i]]\n",
    "            else:\n",
    "                dic[moveTo[i]] = dic[moveFrom[i]]\n",
    "            dic[moveFrom[i]] = 0\n",
    "        print(dic)\n",
    "        ans = []\n",
    "        for k,d in dic.items():\n",
    "            if d > 0:\n",
    "                ans.append(k)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList, SortedSet\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        nums = SortedSet(nums)\n",
    "        for mf, mt in zip(moveFrom, moveTo):\n",
    "            nums.remove(mf)\n",
    "            nums.add(mt)\n",
    "        return sorted(list(set(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "\n",
    "        # arr = list(range(10**5))\n",
    "\n",
    "        d = {}\n",
    "\n",
    "        for f, t in zip(moveFrom[::-1], moveTo[::-1]):\n",
    "            if t not in d:\n",
    "                d[t] = t\n",
    "            d[f] = d[t]\n",
    "        \n",
    "        # print(arr)\n",
    "        ret = set()\n",
    "\n",
    "        for n in nums:\n",
    "            if n not in d:\n",
    "                d[n] = n\n",
    "\n",
    "            ret.add(d[n])        \n",
    "        return list(sorted(ret))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        hashmap = dict()\n",
    "        length = len(moveFrom)\n",
    "        for i in nums:\n",
    "            if i not in hashmap.keys():\n",
    "                hashmap[i] = None\n",
    "        for index in range(length):\n",
    "            del hashmap[moveFrom[index]]\n",
    "            hashmap[moveTo[index]] = None\n",
    "        res = list(sorted(set(hashmap.keys())))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        cnt = {}\n",
    "        for i in nums:\n",
    "            if i in cnt:\n",
    "                cnt[i] += 1\n",
    "            else:\n",
    "                cnt[i] = 1\n",
    "        n = len(moveFrom)\n",
    "        for i in range(n):\n",
    "            cnt[moveFrom[i]] = 0\n",
    "            cnt[moveTo[i]] = 1\n",
    "        res = set()\n",
    "        for i in cnt.keys():\n",
    "            if cnt[i] != 0:\n",
    "                res.add(i)\n",
    "        ress = []\n",
    "        for i in res:\n",
    "            ress.append(i)\n",
    "            \n",
    "        return sorted(ress)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        n = len(moveFrom)\n",
    "        ex = defaultdict(int)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if ex[moveTo[i]]!=0:\n",
    "                ex[moveFrom[i]]=ex[moveTo[i]]\n",
    "            else:\n",
    "                ex[moveFrom[i]]=moveTo[i]\n",
    "        nums = [ex[i] if ex[i]!=0 else i for i in nums]\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        tree_map = OrderedDict()\n",
    "        for item in nums:\n",
    "            tree_map[item] = 1\n",
    "        for i in range(len(moveTo)):\n",
    "            del tree_map[moveFrom[i]]\n",
    "            tree_map[moveTo[i]] = 1\n",
    "        return sorted(tree_map)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        d=defaultdict(int)\n",
    "        for e in nums:\n",
    "            d[e]+=1\n",
    "        for pos in range(len(moveFrom)):\n",
    "            fpos=moveFrom[pos]\n",
    "            tpos=moveTo[pos]\n",
    "            if d[fpos]>0 and fpos!=tpos:\n",
    "                d[tpos]+=d[fpos]\n",
    "                d[fpos]=0\n",
    "        a=[]\n",
    "        for k in d:\n",
    "            if d[k]>0:\n",
    "                a.append((k,d[k]))\n",
    "        a.sort()\n",
    "        return [x[0] for x in a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        c=Counter(nums)\n",
    "        for i in range (0,len(moveFrom)):\n",
    "            x=moveFrom[i]\n",
    "            y=moveTo[i]\n",
    "            if x==y:\n",
    "                continue\n",
    "            c[y]=c[y]+c[x]\n",
    "            del c[x]\n",
    "        ans=[]\n",
    "        p=[[i,c[i]] for i in c]\n",
    "        p.sort()\n",
    "        for i,_ in p:\n",
    "            ans.append(i)        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        dic = defaultdict(int)\n",
    "        for i in nums:\n",
    "            dic[i] = i\n",
    "        for i in range(len(moveFrom)):\n",
    "            f_index = moveFrom[i]\n",
    "            t_index = moveTo[i]\n",
    "\n",
    "            cur = dic[f_index]\n",
    "            dic[f_index] = 0\n",
    "            dic[t_index] = dic[t_index] + cur\n",
    "        res = list({k for k, v in dic.items() if v > 0})\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:\n",
    "        p = {}\n",
    "        for n in nums:\n",
    "            p[n] = 1\n",
    "        \n",
    "        for mf, mt in list(zip(moveFrom, moveTo)):\n",
    "            del p[mf]\n",
    "            p[mt] = 1\n",
    "        \n",
    "        return sorted(p.keys())"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
